package alogrithm.dp;

import java.util.Stack;

public class Fb {
	public int getFb(int n){
		Stack<Integer> queue=new Stack<Integer>();
		queue.push(1);
		queue.push(1);
		int count=1;
		while(!queue.isEmpty()&&queue.size()>1&&count<n-1){
			int second=queue.pop();
			int first=queue.pop();
			
			int sum=second+first;
			queue.push(second);
			queue.push(sum);
			
			count++;
		}
		
		return queue.peek();
	}
	
	
	public int getFbV2(int n){
		int a=1;
		int b=1;
		int s=0;
		for(int i=2;i<n;i++){
			s=a+b;
			a=b;
			b=s;
		}
		return s;
	}
	
	
	
	public static void main(String[] args) {
		Fb fb=new Fb();
		int a=fb.getFbV2(5);
		System.out.println(a);
	}
}
